package priv.pront.code.mati.province.comp;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @Description:
 * @Author: pront
 * @Time:2023-11-18 14:50
 */
public class Main7 {

    static int n;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        while (n-- > 0) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int t1 = -1, t2 = -1;
            int x = 0, y = 0, z = -1, h = -1;
            boolean[][] st = new boolean[n][m];
            boolean flag1 = false;
            boolean flag2 = false;
            char[][] g = new char[n][m];
            Queue<int[]> queue = new LinkedList<>();
            Queue<int[]> queue1 = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                g[i] = scanner.next().toCharArray();
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (g[i][j] == 'P') {
                        x = i; y  = j;
                    }
                }
            }

            queue.add(new int[]{x, y ,0});
            st[x][y] = true;
            while (!queue.isEmpty()) {
                int[] poll = queue.poll();
                if(g[poll[0]][poll[1]] == 'K'){
                    flag1 = true;
                    t1 = poll[2];
                    z = poll[0];
                    h =poll[1];
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = dx[i] + poll[0];
                    int ny = dy[i] + poll[1];
                    if(nx < 0 || nx >= n|| ny < 0 || ny >= m || st[nx][ny] || g[nx][ny] == '#' || g[nx][ny] == 'E') continue;
                    st[nx][ny] = true;
                    queue.add(new int[]{nx, ny, poll[2] + 1});
                }
            }

            if(z == -1){
                System.out.println("No solution");
                continue;
            }
            st = new boolean[n][m];
            queue1.add(new int[]{z, h, 0});
            st[z][h] = true;
            while (!queue1.isEmpty()) {
                int[] poll = queue1.poll();
                if(g[poll[0]][poll[1]] == 'E'){
                    flag2 = true;
                    t2 = poll[2];
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = dx[i] + poll[0];
                    int ny = dy[i] + poll[1];
                    if(nx < 0 || nx >= n|| ny < 0 || ny >= m || st[nx][ny] || g[nx][ny] == '#' ) continue;
                    st[nx][ny] = true;
                    queue1.add(new int[]{nx, ny, poll[2] + 1});
                }
            }

            if (!flag1 || !flag2) {
                System.out.println("No solution");
            }else{
                System.out.println(t1 + t2);
            }

        }
    }
}
